37
37

Sep 21, 2013
09/13

by
Valmir C. Barbosa

texts

######
eye 37

######
favorite 0

######
comment 0

We study the growth of networks from a set of isolated ground nodes by the addition of one new node per time step and also of a fixed number of directed edges leading from the new node to randomly selected nodes already in the network. A fixed-width time window is used so that, in general, only nodes that entered the network within the latest window may receive new incoming edges. The resulting directed network is acyclic at all times and allows some of the ground nodes, then called sinks, to...

Source: http://arxiv.org/abs/0706.3805v1

29
29

Sep 17, 2013
09/13

by
Valmir C. Barbosa

texts

######
eye 29

######
favorite 0

######
comment 0

We introduce the notion of a network's conduciveness, a probabilistically interpretable measure of how the network's structure allows it to be conducive to roaming agents, in certain conditions, from one portion of the network to another. We exemplify its use through an application to the two problems in combinatorial optimization that, given an undirected graph, ask that its so-called chromatic and independence numbers be found. Though NP-hard, when solved on sequences of expanding random...

Source: http://arxiv.org/abs/1003.1412v1

31
31

Sep 21, 2013
09/13

by
Valmir C. Barbosa

texts

######
eye 31

######
favorite 0

######
comment 0

Given two subsets A and B of nodes in a directed graph, the conduciveness of the graph from A to B is the ratio representing how many of the edges outgoing from nodes in A are incoming to nodes in B. When the graph's nodes stand for the possible solutions to certain problems of combinatorial optimization, choosing its edges appropriately has been shown to lead to conduciveness properties that provide useful insight into the performance of algorithms to solve those problems. Here we study the...

Source: http://arxiv.org/abs/1204.6181v1

39
39

Sep 23, 2013
09/13

by
Andre Nathan; Valmir C. Barbosa

texts

######
eye 39

######
favorite 0

######
comment 0

An information-theoretic framework known as integrated information theory (IIT) has been introduced recently for the study of the emergence of consciousness in the brain [D. Balduzzi and G. Tononi, PLoS Comput. Biol. 4, e1000091 (2008)]. IIT purports that this phenomenon is to be equated with the generation of information by the brain surpassing the information which the brain's constituents already generate independently of one another. IIT is not fully plausible in its modeling assumptions,...

Source: http://arxiv.org/abs/1012.5649v1

25
25

Sep 22, 2013
09/13

by
Andre Nathan; Valmir C. Barbosa

texts

######
eye 25

######
favorite 0

######
comment 0

When a neuron fires and the resulting action potential travels down its axon toward other neurons' dendrites, the effect on each of those neurons is mediated by the weight of the synapse that separates it from the firing neuron. This weight, in turn, is affected by the postsynaptic neuron's response through a mechanism that is thought to underlie important processes such as learning and memory. Although of difficult quantification, cortical synaptic weights have been found to obey a long-tailed...

Source: http://arxiv.org/abs/0906.3252v1

36
36

Sep 21, 2013
09/13

by
Elias Bareinboim; Valmir C. Barbosa

texts

######
eye 36

######
favorite 0

######
comment 0

The load of a node in a network is the total traffic going through it when every node pair sustains a uniform bidirectional traffic between them on shortest paths. We show that nodal load can be expressed in terms of the more elementary notion of a node's descents in breadth-first-search (BFS or shortest-path) trees, and study both the descent and nodal-load distributions in the case of scale-free networks. Our treatment is both semi-analytical (combining a generating-function formalism with...

Source: http://arxiv.org/abs/0712.3924v1

27
27

Sep 23, 2013
09/13

by
Fabio R. J. Vieira; Valmir C. Barbosa

texts

######
eye 27

######
favorite 0

######
comment 0

The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly is the minimum tile set problem (MTSP), which asks for a collection of types of elementary objects (called tiles) to be...

Source: http://arxiv.org/abs/0710.0672v2

28
28

Sep 18, 2013
09/13

by
Rodrigo S. C. Leao; Valmir C. Barbosa

texts

######
eye 28

######
favorite 0

######
comment 0

A cycle double cover (CDC) of an undirected graph is a collection of the graph's cycles such that every edge of the graph belongs to exactly two cycles. We describe a constructive method for generating all the cubic graphs that have a 6-CDC (a CDC in which every cycle has length 6). As an application of the method, we prove that all such graphs have a Hamiltonian cycle. A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably...

Source: http://arxiv.org/abs/cs/0505088v4

26
26

Sep 18, 2013
09/13

by
Ricardo C. Correa; Valmir C. Barbosa

texts

######
eye 26

######
favorite 0

######
comment 0

Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different...

Source: http://arxiv.org/abs/cs/0611165v1

37
37

Sep 19, 2013
09/13

by
Fabiano de S. Oliveira; Valmir C. Barbosa

texts

######
eye 37

######
favorite 0

######
comment 0

We revisit the deadlock-prevention problem by focusing on priority digraphs instead of the traditional wait-for digraphs. This has allowed us to formulate deadlock prevention in terms of prohibiting the occurrence of directed cycles even in the most general of wait models (the so-called AND-OR model, in which prohibiting wait-for directed cycles is generally overly restrictive). For a particular case in which the priority digraphs are somewhat simplified, we introduce a Las Vegas probabilistic...

Source: http://arxiv.org/abs/1010.4411v1

34
34

Sep 19, 2013
09/13

by
Renato C. Dutra; Valmir C. Barbosa

texts

######
eye 34

######
favorite 0

######
comment 0

We consider networks of anonymous sensors and address the problem of constructing routes for the delivery of information from a group of sensors in response to a query by a sink. In order to circumvent the restrictions imposed by anonymity, we rely on using the power level perceived by the sensors in the query from the sink. We introduce a simple distributed algorithm to achieve the building of routes to the sink and evaluate its performance by means of simulations.

Source: http://arxiv.org/abs/cs/0507021v1

33
33

Sep 19, 2013
09/13

by
Luis O. Rigo Jr.; Valmir C. Barbosa

texts

######
eye 33

######
favorite 0

######
comment 0

Correlated time series are time series that, by virtue of the underlying process to which they refer, are expected to influence each other strongly. We introduce a novel approach to handle such time series, one that models their interaction as a two-dimensional cellular automaton and therefore allows them to be treated as a single entity. We apply our approach to the problems of filling gaps and predicting values in rainfall time series. Computational results show that the new approach compares...

Source: http://arxiv.org/abs/cs/0507023v1

29
29

Sep 23, 2013
09/13

by
Alexandre O. Stauffer; Valmir C. Barbosa

texts

######
eye 29

######
favorite 0

######
comment 0

We consider the problem of distributing a vaccine for immunizing a scale-free network against a given virus or worm. We introduce a new method, based on vaccine dissemination, that seems to reflect more accurately what is expected to occur in real-world networks. Also, since the dissemination is performed using only local information, the method can be easily employed in practice. Using a random-graph framework, we analyze our method both mathematically and by means of simulations. We...

Source: http://arxiv.org/abs/cs/0511080v1

28
28

Sep 18, 2013
09/13

by
Rodolfo M. Pussente; Valmir C. Barbosa

texts

######
eye 28

######
favorite 0

######
comment 0

We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diameter. Clock-synchronization messages are only sent as part of the communication, assumed reasonably frequent, that already takes place among nodes. The algorithm has the gradient property of [2], achieving an O(1) worst-case skew between the logical clocks of neighbors. As in the case of...

Source: http://arxiv.org/abs/0704.3890v1

40
40

Sep 22, 2013
09/13

by
Rodrigo S. C. Leao; Valmir C. Barbosa

texts

######
eye 40

######
favorite 0

######
comment 0

When we represent a network of sensors in Euclidean space by a graph, there are two distances between any two nodes that we may consider. One of them is the Euclidean distance. The other is the distance between the two nodes in the graph, defined to be the number of edges on a shortest path between them. In this paper, we consider a network of sensors placed uniformly at random in a two-dimensional region and study two conditional distributions related to these distances. The first is the...

Source: http://arxiv.org/abs/0812.3259v1

21
21

Sep 22, 2013
09/13

by
Valmir C. Barbosa; Raul Donangelo; Sergio R. Souza

texts

######
eye 21

######
favorite 0

######
comment 0

We study directed random graphs (random graphs whose edges are directed) as they evolve in discrete time by the addition of nodes and edges. For two distinct evolution strategies, one that forces the graph to a condition of near acyclicity at all times and another that allows the appearance of nontrivial directed cycles, we provide analytic and simulation results related to the distributions of degrees. Within the latter strategy, in particular, we investigate the appearance and behavior of the...

Source: http://arxiv.org/abs/cond-mat/0309442v1

3
3.0

Jun 27, 2018
06/18

by
Rodrigo R. Esch; Fábio Protti; Valmir C. Barbosa

texts

######
eye 3

######
favorite 0

######
comment 0

Given a connected region in two-dimensional space where events of a certain kind occur according to a certain time-varying density, we consider the problem of setting up a network of autonomous mobile agents to detect the occurrence of those events and possibly record them in as effective a manner as possible. We assume that agents can communicate with one another wirelessly within a fixed communication radius, and moreover that initially no agent has any information regarding the event...

Topics: Networking and Internet Architecture, Computing Research Repository, Multiagent Systems

Source: http://arxiv.org/abs/1506.01310

31
31

Sep 18, 2013
09/13

by
Valmir C. Barbosa; Raul Donangelo; Sergio R. Souza

texts

######
eye 31

######
favorite 0

######
comment 0

We study network growth from a fixed set of initially isolated nodes placed at random on the surface of a sphere. The growth mechanism we use adds edges to the network depending on strictly local gain and cost criteria. Only nodes that are not too far apart on the sphere may be considered for being joined by an edge. Given two such nodes, the joining occurs only if the gain of doing it surpasses the cost. Our model is based on a multiplicative parameter lambda that regulates, in a function of...

Source: http://arxiv.org/abs/0707.1821v1

24
24

Sep 22, 2013
09/13

by
Valmir C. Barbosa; Raul Donangelo; Sergio R. Souza

texts

######
eye 24

######
favorite 0

######
comment 0

We study directed random graphs (random graphs whose edges are directed), and present new results on the so-called strong components of those graphs. We provide analytic and simulation results on two special classes of strong component, called cycle components and knots, which are important in random networks that represent certain computational systems.

Source: http://arxiv.org/abs/cond-mat/0309439v1

54
54

Jul 19, 2013
07/13

by
Valmir C. Barbosa; Raul Donangelo; Sergio R. Souza

texts

######
eye 54

######
favorite 0

######
comment 0

In evolutionary dynamics, the probability that a mutation spreads through the whole population, having arisen in a single individual, is known as the fixation probability. In general, it is not possible to find the fixation probability analytically given the mutant's fitness and the topological constraints that govern the spread of the mutation, so one resorts to simulations instead. Depending on the topology in use, a great number of evolutionary steps may be needed in each of the simulation...

Source: http://arxiv.org/abs/1005.3244v1

48
48

Sep 23, 2013
09/13

by
Flavio B. Gonzaga; Valmir C. Barbosa; Geraldo B. Xexéo

texts

######
eye 48

######
favorite 0

######
comment 0

We study the network structure of Wikipedia (restricted to its mathematical portion), MathWorld, and DLMF. We approach these three online mathematical libraries from the perspective of several global and local network-theoretic features, providing for each one the appropriate value or distribution, along with comparisons that, if possible, also include the whole of the Wikipedia or the Web. We identify some distinguishing characteristics of all three libraries, most of them supposedly traceable...

Source: http://arxiv.org/abs/1212.3536v1

24
24

Sep 22, 2013
09/13

by
Valmir C. Barbosa; Raul Donangelo; Sergio R. Souza

texts

######
eye 24

######
favorite 0

######
comment 0

Natural selection and random drift are competing phenomena for explaining the evolution of populations. Combining a highly fit mutant with a population structure that improves the odds that the mutant spreads through the whole population tips the balance in favor of natural selection. The probability that the spread occurs, known as the fixation probability, depends heavily on how the population is structured. Certain topologies, albeit highly artificially contrived, have been shown to exist...

Source: http://arxiv.org/abs/0812.2327v1

39
39

Sep 21, 2013
09/13

by
Fabio R. J. Vieira; José F. de Rezende; Valmir C. Barbosa; Serge Fdida

texts

######
eye 39

######
favorite 0

######
comment 0

We consider wireless mesh networks and the problem of scheduling the links of a given set of routes under the assumption of a heavy-traffic pattern. We assume some TDMA protocol provides a background of synchronized time slots and seek to schedule the routes' links to maximize the number of packets that get delivered to their destinations per time slot. Our approach is to construct an undirected graph G and to heuristically obtain node multicolorings for G that can be turned into efficient link...

Source: http://arxiv.org/abs/1106.1590v1

0
0.0

Jun 27, 2018
06/18

by
Fabio R. J. Vieira; José F. de Rezende; Valmir C. Barbosa

texts

######
eye 0

######
favorite 0

######
comment 0

Scheduling wireless links for simultaneous activation in such a way that all transmissions are successfully decoded at the receivers and moreover network capacity is maximized is a computationally hard problem. Usually it is tackled by heuristics whose output is a sequence of time slots in which every link appears in exactly one time slot. Such approaches can be interpreted as the coloring of a graph's vertices so that every vertex gets exactly one color. Here we introduce a new approach that...

Topics: Computing Research Repository, Networking and Internet Architecture

Source: http://arxiv.org/abs/1504.01647

32
32

Sep 20, 2013
09/13

by
Valmir C. Barbosa; Fernando M. L. Ferreira; Daniel V. Kling; Eduardo Lopes; Fabio Protti; Eber A. Schmitz

texts

######
eye 32

######
favorite 0

######
comment 0

In this work we deal with a mechanism for process simulation called a NonDeterministic Stochastic Activity Network (NDSAN). An NDSAN consists basically of a set of activities along with precedence relations involving these activities, which determine their order of execution. Activity durations are stochastic, given by continuous, nonnegative random variables. The nondeterministic behavior of an NDSAN is based on two additional possibilities: (i) by associating choice probabilities with groups...

Source: http://arxiv.org/abs/cs/0612140v2